16. CODE: Find the Closest Node

Find the Closest Node

L4 Before Find The Closest Node

In the upcoming exercises, you will start working on the RoutePlanner class, which will contain methods to perform the A* search. To conduct a search, a RoutePlanner class instance will first be initialized starting and ending coordinates provided by the user as float values. However, this presents a problem: these float values might not exactly correspond to any given node on the map.

in order for the search to be performed with the map data, you will be finding a path between two nodes. This means that you need to find the nodes in the RouteModel that are closest to the starting and ending coordinates given by the user. In this exercise, you will write a method FindClosestNode that accepts two floats and finds the closest node in your model.

Note that while it might be tempting to just iterate over all nodes in the SNodes() vector to find the closest node, in practice, that will not turn out well. Many nodes in the OSM data are on closed paths or may be isolated is some other way. If you choose one one of these nodes, you may not be able to find a path from that node to the end node. To avoid this, you will choose the closest node that is on a road that is not a footway. In other words, a node that is not of Model::Road::Type::Footway type.

## To complete this exercise:

  1. Add a public method declaration FindClosestNode in the RouteModel class in route_model.h. This method should accept two floats x and y as arguments, and should return a reference to a RouteModel::Node object.
  2. Add a method definition route_model.cpp
  3. In the body of the method, you will need to do the following:
  1. Create a temporary Node with x and y coordinates given by the method inputs.
    1. Create a float min_dist = std::numeric_limits<float>::max() for the minum distance found in your search.
    2. Create an int variable closest_idx to store the index of the closest
    3. Write a loop that iterates through the vector given by calling Roads().
    4. For each reference &road in the vector, check that the type is not a footway: road.type != Model::Road::Type::Footway. If the road is not a footway:
      1. Loop over each node index in the way that the road belongs to: Ways()[road.way].nodes.
      2. Update closest_idx and min_dist, if needed.
    5. Return the node from the SNodes() vector using the found index.

Workspace

This section contains either a workspace (it can be a Jupyter Notebook workspace or an online code editor work space, etc.) and it cannot be automatically downloaded to be generated here. Please access the classroom with your account and manually download the workspace to your local machine. Note that for some courses, Udacity upload the workspace files onto https://github.com/udacity, so you may be able to download them there.

Workspace Information:

  • Default file path:
  • Workspace type: react
  • Opened files (when workspace is loaded): n/a
  • userCode:

    export CXX=g++-7
    export CXXFLAGS=-std=c++17
    cmake_tests() {
    /usr/local/bin/cmake -DTESTING="FindClosest" "$1"
    }
    export -f cmake_tests

Solution

Find Closest Node

Next Concept